package com.heima.leetcode.practice;

import java.util.Arrays;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 16. 最接近的三数之和
 * @date 2025/3/11 11:01
 */
public class E16 {

    /**
     * 最接近的三数之和
     */
    private int closest = Integer.MAX_VALUE;

    /**
     * <h3>方法一：回溯</h3>
     *
     * @param nums   数组
     * @param target 三个数和的目标值
     * @return 最接近目标值的和
     */
    public int threeSumClosest1(int[] nums, int target) {
        dfs(nums, target, 0, 0, 1);
        return closest;
    }

    /**
     * 回溯
     *
     * @param nums    数组
     * @param target  三个数和的目标值
     * @param start   开始位置
     * @param currSum 当前和
     * @param length  当前长度
     */
    private void dfs(int[] nums, int target, int start, int currSum, int length) {
        if (start == nums.length) return;
        for (int i = start; i < nums.length; i++) {
            if (length == 3) {
                int sum = currSum + nums[i];
                if (Math.abs(target - sum) < Math.abs(target - closest)) {
                    closest = sum;
                }
                continue; // 可以在这里加continue也可以在一开始加个length == 4的if判断
            }
            dfs(nums, target, i + 1, currSum + nums[i], length + 1);
        }
    }

    /**
     * <h3>方法二：双指针配合二分查找的类似思想，效率最高</h3>
     *
     * @param nums   数组
     * @param target 目标值
     * @return 最接近目标值的和
     */
    public int threeSumClosest2(int[] nums, int target) {
        // 1. 先排序，好好后面进行双指针操作
        Arrays.sort(nums);
        // 2. 初始化closest为前三个最小的之和
        int closest = nums[0] + nums[1] + nums[2];
        // 3. 遍历数组，每次都会确定三个数的第一个数，一次循环内的任务就是确定另外两个数加起来离目标值最接近
        for (int i = 0; i < nums.length - 2; i++) {
            // 3.1 双指针，left从i+1开始，right从数组末尾开始
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                // 3.2 计算当前三个数的和，如果比原来的closest更接近目标值，更新closest
                int sum = nums[i] + nums[left] + nums[right];
                if (Math.abs(target - sum) < Math.abs(target - closest)) {
                    closest = sum;
                }
                // 3.3 根据当前三个数的和与目标值的大小关系，移动指针
                if (sum > target) {
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    return sum;
                }
            }
        }
        // 4. 返回closest
        return closest;
    }
}
